1. Field of the Invention
This invention generally relates to queue architectures and more particularly relates to a fault tolerant queue architecture in a multiprocessor environment.
2. Description of the Prior Art
The use of the queue construct has been widespread in the design of general purpose data processing systems. An exemplary general application of a queue may involve a first processor that puts items in a queue and a second processor that gets items from the queue, wherein each of the items in the queue represents a task to be performed. If each of the tasks (items in the queue) may be performed independent of the other tasks in the queue, then additional processors could be included to put tasks in and get tasks from the queue.
Fault tolerance may be a desirable characteristic in a queue design, depending upon the application in which the queue is used. If fault tolerance is desired in a system having a first processor for putting tasks into a queue and a second processor for getting tasks from the queue and performing the tasks, then the queue architecture must ensure that if the second processor fails in getting a task from the queue, the task is not simply lost.
If, in addition to fault tolerance, multiple processors have access to the queue for performance considerations, then the queue design must ensure that the adverse impact on performance which may be caused by the fault tolerance mechanism is minimized.
U.S. Pat. No. 5,265,229 to Sareen which is entitled "Single Load, Multiple Issue Queue with Error Recovery Capability" (hereinafter '229) describes a dual access queuing system in the context of data transfer logic within a data processing system. The queuing system entails dual circuitry for reading from the queue. The first read circuitry reads odd entries from the queue, and the second read circuitry reads even entries. While the first read circuitry is waiting for acknowledgement from the device designated to receive the queue entry, the second circuitry may commence transfer of another (even) queue entry. If transmission of the queue entry by the first read circuitry fails, it retransmits the queue entry. It can be seen that each read circuitry must wait for acknowledgment from the receiving unit before another queue entry is read. Furthermore, if the first read circuitry becomes inoperable while the second read circuitry remains operable, the second read circuitry is unable to recover for the first because it is dedicated to reading one set of addresses from the queue.
It would therefore be desirable to have a multiprocessor queuing system which is fault tolerant and in which processing performance is not adversely impacted by such fault tolerance.